// DynamicProgramming.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> maxProfile(vector<int> const& data)
{
    vector<pair<int, int>> ret;
    vector<pair<int, int>> segs;

    for (size_t i = 0; i < data.size() - 1; ++i)
    {
        for (size_t j = i + 1; j < data.size(); ++j)
        {
            if (data[j] - data[i] > 0)
            {
                segs.push_back(make_pair(i, j));
            }
        }
    }

    if (segs.size() == 0)
    {
        return ret;
    }
    else if (segs.size() == 1)
    {
        ret.push_back(segs[0]);
        return ret;
    }

    auto profile = [&](pair<int, int> const& seg)
    {
        return data[seg.second] - data[seg.first];
    };

    auto printSegs = [&]()
    {
        for (auto seg : segs)
        {
            cout << profile(seg) << ", ";
        }
        cout << endl;
    };

    sort(segs.begin(), segs.end(), [&](pair<int, int> const& left, pair<int, int> const& right)
    {
        return profile(left) > profile(right);
    });

    printSegs();

    for (size_t i = 0; i < segs.size() - 1; ++i)
    {
        for (size_t j = i + 1; j < segs.size(); ++j)
        {
            if (segs[i].second < segs[j].first ||
                segs[i].first > segs[j].second)
            {
                auto value = profile(segs[i]) + profile(segs[j]);
                if (value > profile(segs[0]))
                {
                    ret.push_back(segs[i]);
                    ret.push_back(segs[j]);
                }
                else
                {
                    ret.push_back(segs[0]);
                }
                return ret;
            }
        }
    }

    ret.push_back(segs[0]);
    return ret;
}

void testMaxProfile()
{
    //Say you have an array for which the i - th element is the price of a given stock on day i.
    //    Design an algorithm to find the maximum profit.You may complete at most two transactions.
    //Note: You may not engage in multiple transactions at the same time(ie, you must sell the stock before
    //        you buy again).

    int data[] = {2, 5, 6, 8, 9 , 3, 4, 7, 1, 6, 3, 2};
    auto ret = maxProfile(vector<int>(begin(data), end(data)));
    for (auto seg : ret)
    {
        cout << data[seg.second] - data[seg.first] << ", " << endl;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    testMaxProfile();
    cin.get();
	return 0;
}

